package com.hot100;

import java.util.*;

public class h018 {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> res =new ArrayList<>();
        Set<List<Integer>> set = new HashSet<>();
        for (int i=0; i<nums.length; i++){
            for (int j = i+1;j<nums.length;j++){
                int left = j+1,right = nums.length-1;
                while (left<right){
                    int sum = nums[i]+nums[j]+nums[left]+nums[right];
                    if (sum == target){
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[left]);
                        list.add(nums[right]);
                        boolean flag = set.add(list);
                        if (flag)
                        res.add(list);
                    }
                    if (sum > target)
                        right --;
                    else
                        left ++;
                }
            }
        }
        return res;
    }
}
